package dmsxl.tanxin;

/**
 * Author: Zhang Dongwei
 * Date: 2023/8/1 15:30
 */
public class tx22_738 {

    public static void main(String[] args) {
        System.out.println(monotoneIncreasingDigits(777616726));
    }

    //    答案(多出parsint影响效率)
    public static int monotoneIncreasingDigits2(int n) {
        String[] s = (n + "").split("");
        int flag = s.length;
        for (int i = s.length - 1; i > 0; i--) {
            if (Integer.parseInt(s[i]) < Integer.parseInt(s[i - 1])) {
                s[i - 1] = (Integer.parseInt(s[i - 1]) - 1) + "";
                flag = i;
            }
        }
        for (int i = flag; i < s.length; i++) {
            s[i] = "9";
        }
        return Integer.parseInt(String.join("", s));
    }

    //    答案
    public static int monotoneIncreasingDigits(int n) {
        String s = String.valueOf(n);
        char[] chars = s.toCharArray();
        int start = s.length();
        for (int i = s.length() - 2; i >= 0; i--) {
            if (chars[i] > chars[i + 1]) {
                chars[i]--;
                start = i + 1;
            }
        }
        for (int i = start; i < s.length(); i++) {
            chars[i] = '9';
        }
        return Integer.parseInt(String.valueOf(chars));
    }

    //    自己写的，超时
    public static int monotoneIncreasingDigits1(int n) {
        int m = n;
        while (m >= 0) {
            if (judge(m)) return m;
            m--;
        }
        return -1;
    }

    public static boolean judge(int n) {
        String s = n + "";
        int l = s.length();
        for (int i = 0; i < l - 1; i++) {
            if (s.charAt(i) > s.charAt(i + 1)) return false;
        }
        return true;
    }
}
